package zuo.highLevel_8;

/**
 * @Author: Forx
 * @Data: 2021/7/11
 * @Desc: Algorithm - zuo.highLevel_8
 * @Version: v1.0
 */
/**
 * 判定一个由[a-z]字符构成的字符串和一个包含'?'和'*'通配符的字符串是否匹配。
 * 通配符'?'匹配任意单一字符，'*'匹配任意多个字符包括0个字符。
 * 字符串长度不会超过100,字符串不为空。
 * 输入描述：
 * 字符串str和包含通配符的字符串pattern。1<=字符串长度<=100输出描述：
 * true表示匹配，false表示不匹配
 * */
class PIPEI{
    public boolean piPei(char[] src,char[] pattern){
        return process(src,pattern,0,0);
    }
    private boolean process(char[] src,char[] pattern,int sI,int pI){
        if(pI==pattern.length){
            return sI==src.length;
        }
        if(pI+1==pattern.length || pattern[pI+1]!='*'){
            return sI!= src.length && (src[sI] == pattern[pI]||pattern[pI]=='.')&&(
                    process(src, pattern, sI+1, pI+1)
                    );

        }
        while (sI!= src.length && (src[sI] == pattern[pI])|| pattern[pI]=='.'){
            if(process(src, pattern, sI, pI+2)){
                return true;
            }
            sI++;
        }
        return process(src, pattern, sI, pI+2);
    }

    private boolean processDP(char[] src,char[] pattern){
//        boolean[][] dp = new boolean[src.length+1][pattern.length+1];
//        dp[src.length][pattern.length] = true;
//        for (int i = 0; i <= src.length; i++) {
//            dp[i][pattern.length]=false;
//        }
//        for (int pi = pattern.length-1; pi >=0 ;) {
//            for (int si = src.length; si >=0;) {
//                if(pi+1==pattern.length || pattern[pi+1]!='*'){
//                    dp[si][pi] = si!= src.length && (src[si] == pattern[pi]||pattern[pi]=='.')&&(
//                            dp[si+1][pi+1]
//                    );
//                    si--;
//                }else {
//                    int sicpy = si;
//                    while (sicpy!= src.length && (src[sicpy] == pattern[pi])|| pattern[pi]=='.'){
//                        if(dp[sicpy][pi+2]){
//                            dp[si][pi] =true;
//                            break;
//                        }
//                        sicpy++;
//                    }
//                }
//
//
//        }
//        //pi = pattern.length -1
//        for (int i = src.length-1; i >= 0; i--) {
//            dp[i][pattern.length-1] = (src[i] == pattern[pattern.length-1] || pattern[pattern.length-1] == '.')&&dp[i+1][pattern.length];
//        }
//        //pattern[pi+1]!='*'
//        for (int si = src.length-1; si >=0; si--) {
//            for (int pi = 0; pi < pattern.length - 1; pi++) {
//                if(pattern[pi+1]!='*'){
//                    dp[si][pi] = (src[si] == pattern[pattern.length-1] || pattern[pattern.length-1] == '.')&&dp[si+1][pattern.length];
//                }
//            }
//        }
//        for (int pi = pattern.length-2; pi >=0; pi-=2) {
//            for (int si = 0; si < src.length&& (src[si] == pattern[pi])|| pattern[pi]=='.'; si++) {
//                if(dp[si][pi+2]){
//                    dp[si][pi]=true;
//                    break;
//                }
//            }
//        }
//        for (int pi = 0; pi < pattern.length - 2; pi++) {
//
//        }
//
//        }


        return false;
    }

}

/**
 *
 * 数组异或和的定义：把数组中所有的数异或起来得到的值
 * 给定一个整型数组arr,其中可能有正、有负、有零，求其中子数组的最大异或和
 * 【举例】
 * arr = {3}
 * 数组只有1个数，所以只有一个子数组，就是这个数组本身，最大异或和为3
 * arr = {3,-28,-29,2}
 * 子数组有很多，但是{-28,-29}这个子数组的异或和为7,是所有子数组中最大的
 *
 * 前缀树,尽量找1
 */

class MAXEOR{

}

/**
 * 给定一个数组arr,代表一排有分数的气球。每打爆一个气球都能获得分数，假设打爆气
 * 球的分数为X,获得分数的规则如下：
 * 1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为
 * L;如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为
 * R。获得分数为L*X*R。
 * 2)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为
 * L;如果被打爆气球的右边所有气球都已经被打爆。获得分数为L*X。
 * 3)如果被打爆气球的左边所有的气球都已经被打爆；如果被打爆气球的右边有没被打爆的
 * 气球，找到离被打爆气球最近的气球，假设分数为R;如果被打爆气球的右边所有气球都
 * 已经被打爆。获得分数为X*R。I
 * 4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为X。
 * 目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同
 * 的
 * 总分，请返回能获得的最大分数。
 * 204
 * 【举例】
 * arr = {3,2,5}
 * 如果先打爆3,获得3*2;再打爆2,获得2*5;最后打爆5,获得5;最后总分21
 * 如果先打爆3,获得3*2;再打爆5,获得2*5;最后打爆2,获得2;最后总分18
 * 如果先打爆2,获得3*2*5;再打爆3,获得3*5;最后打爆5,获得5;最后总分50
 * 如果先打爆2,获得3*2*5;再打爆5,获得3*5;最后打爆3,获得3;最后总分48
 * 如果先打爆5,获得2*5;再打爆3,获得3*2;最后打爆2,获得2;最后总分18
 * 如果先打爆5,获得2*5;再打爆2,获得3*2;最后打爆3,获得3;最后总分19
 * 返回能获得的最大分数为50
 *
 * */
class BOOM{

}

/**
 * [与汉诺塔不是一个问题]
 *汉诺塔游戏的要求把所有的圆盘从左边都移到右边的柱子上，给定一个整型数组arr,
 * 其中只含有1、2和3,代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，
 * arr[i]的值代表第i+1个圆盘的位置。
 * 比如，arr=[3,3,2,1],代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中
 * 柱上、第4个圆盘在左柱上
 * 如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨
 * 迹中的第几个状态；如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。
 *
 * */


public class HL8 {
}
